Atlantic City algorithm is a

probabilistic Probability is the branch of mathematics concerning numerical descriptions of how likely an Event (probability theory), event is to occur, or how likely it is that a proposition is true. The probability of an event is a number between 0 and ...

polynomial time In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...

algorithm In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algorithms are used as specificat ...

that answers correctly at least 75% of the time (or, in some versions, some other value greater than 50%). The term "Atlantic City" was first introduced in 1982 by J. Finn in an unpublished manuscript entitled ''Comparison of probabilistic tests for primality''. Two other common classes of probabilistic algorithms are

Monte Carlo algorithm In computing, a Monte Carlo algorithm is a randomized algorithm whose output may be incorrect with a certain (typically small) probability. Two examples of such algorithms are Karger–Stein algorithm and Monte Carlo algorithm for minimum Feedba ...

s and

Las Vegas algorithm In computing, a Las Vegas algorithm is a randomized algorithm that always gives correct results; that is, it always produces the correct result or it informs about the failure. However, the runtime of a Las Vegas algorithm differs depending on the ...

s. Monte Carlo algorithms are always fast, but only probably correct. On the other hand, Las Vegas algorithms are always correct, but only probably fast. The Atlantic City algorithms, which are bounded probabilistic polynomial time algorithms are probably correct and probably fast.

References

Randomized algorithms {{comp-sci-theory-stub

See also

References